package com.banmao.CarlCamp.Day06;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/3sum/
 */
@Slf4j
public class LC15 {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return result;
    }

    // 错误原因在于没有去重 考虑 [0, 0, 0, 0]
    public List<List<Integer>> threeSum_fault(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) {
            return res;
        }
        // 没有想法
        // 看了卡哥的思路，首先哈希法不可取，因为题目要求元组不重复，而哈希法得到结果后还要进行去重操作，两次哈希的效率极低
        // 卡哥推荐三指针法，使用双指针的前提是数组有序
        Arrays.sort(nums);

        // 三个指针，两个分别指向首尾，另一个从首指针后面开始往后遍历，遇到尾指针则首指针移动，中间指针重新开始遍历
        // 当三数之和小于0，首指针移动；当三数之和大于0，则尾指针移动
        int left = 0, right = nums.length - 1, i = 1;
        while (left != right) {
            if (i >= right) {
                left++;
                while (nums[left] == nums[left - 1] && left < right) {
                    left++;
                }
                i = left + 1;
                continue;
            }
            int sum = nums[left] + nums[right] + nums[i];
            if (sum > 0) {
                right--;
                i = left + 1;
            } else if (sum < 0) {
                left++;
                i = left + 1;
            } else {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                while (right > i && nums[right] == nums[right - 1]) right--;
                while (right > i && nums[i] == nums[i + 1]) i++;
                i++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        LC15 lc15 = new LC15();
        List<List<Integer>> res = lc15.threeSum(new int[]{-2,0,1,1,2});
        log.info("{}", res);
    }

}
